package com.yanceysong.codetop.s71_s80;


public class S72_Easy_122_买卖股票的最佳时机_II {
    /**
     * .<p>
     * .题目链接：<a href="https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/">https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/</a>
     * .<p>
     * .给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。你可以在每一天选择：
     * .1. 买入一股（前提：当前未持有）
     * .2. 卖出所持有的一股（前提：当前持有）
     * .3. 不操作
     * .并且：
     * .- 任意时刻最多只能持有 1 股股票；
     * .- 可以在同一天「买入再卖出」（相当于捕获当天的正差价）；
     * .目标：最大化累计利润。
     * .<p>
     * .示例 1：
     * .输入：prices = [7,1,5,3,6,4]
     * .输出：7
     * .解释：
     * .第2天买(1)第3天卖(5) 获得 4；第4天买(3)第5天卖(6) 获得 3；总利润 4+3=7。
     * .<p>
     * .示例 2：
     * .输入：prices = [1,2,3,4,5]
     * .输出：4
     * .解释：持续上升，只需第1天买，第5天卖=4；也可视为每天都赚 (2-1)+(3-2)+(4-3)+(5-4)=4。
     * .<p>
     * .示例 3：
     * .输入：prices = [7,6,4,3,1]
     * .输出：0
     * .解释：始终下降，不进行任何交易获最大利润 0。
     * .<p>
     * .=====================
     * .核心标签 / Tags：
     * .贪心 / 动态规划 / 数组 / 股票问题状态机
     * .=====================
     * <p>
     * .【核心洞察 Greedy Insight】
     * .允许无限次交易(但不能同时持有多股)，相当于把所有「上涨的相邻差值」累加即可：
     * .只要今天价格 > 昨天价格，就把差价计入利润 —— 等价于在所有上升段内：低点买、高点卖。
     * .证明直觉：一段连续上升区间 [a,b,c,d] (a<b<c<d)
     * .   合并一次交易利润 = d - a
     * .   拆分多次交易利润 = (b-a)+(c-b)+(d-c) = d - a  相等
     * .所以把所有正的差值加起来即可得到最大利润。
     * <p>
     * .ASCII 上升/下降走势示意：
     * .Day:    1  2  3  4  5  6
     * .Price:  7  1  5  3  6  4
     * .         \\    /   \\   /
     * .          ▼  ▲     ▼ ▲
     * .捕获： (5-1)=4  +  (6-3)=3  => 7
     * <p>
     * .【状态机 / DP 视角】(更通用的写法，便于扩展为含手续费/冷冻期等变种)
     * .定义：
     * .  dp[i][0] 第 i 天结束时 不持有股票 的最大利润
     * .  dp[i][1] 第 i 天结束时 持有股票 的最大利润
     * .转移：
     * .  dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])  (今天不持有：要么昨天就不持有，要么今天卖出)
     * .  dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])  (今天持有：要么昨天就持有，要么今天买入)
     * .初始：
     * .  dp[0][0] = 0 (第一天不持有利润为0)
     * .  dp[0][1] = -prices[0] (第一天如果持有，相当于买入花费)
     * .答案：dp[n-1][0]
     * .空间优化：只需两个变量迭代即可。
     * <p>
     * .【DP 状态机 ASCII 图】(两个状态之间的日内转换)：
     * .每一天 i：
     * .  ┌──────────────────────────────────────────────┐
     * .  │          (卖出 获得 +price[i])               │
     * .  │  持有状态 hold[i] ─────────────────▶ 不持有状态 cash[i] │
     * .  │        ▲                                      │
     * .  │        │ (买入 支出 -price[i])                 │
     * .  │        └──────────────────────────────────────┘
     * .  转移：
     * .    cash[i] = max(cash[i-1], hold[i-1] + price[i])  // 继续空仓 或 今天卖出
     * .    hold[i] = max(hold[i-1], cash[i-1] - price[i])  // 继续持仓 或 今天买入
     * .  最终答案 = cash[n-1]
     * <p>
     * .【复杂度分析】
     * .- 贪心：时间 O(n)，空间 O(1)
     * .- DP：  时间 O(n)，空间 O(1) (优化后)
     * <p>
     * .【边界与鲁棒性】
     * .- prices 为空或长度 < 2：直接返回 0
     * .- 全下降：返回 0
     * .- 单元素：返回 0
     * .- 大量震荡：算法仍只累计正差值
     * <p>
     * .【何时选 DP？】
     * .当题目引入：手续费、冷冻期、限交易次数、同时持有多股等约束时，贪心不再适用，用状态机 DP 演化即可。
     * <p>
     * .【总结】
     * .本题最佳实现 = 简单贪心；DP 版本作为教育性补充，帮助理解后续扩展题型。
     */
    public int maxProfit(int[] prices) {
        int ans = 0;
        for (int i = 1; i < prices.length; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }

    /**
     * .动态规划（状态机）实现：跟踪两个互斥状态的最优值
     * <p>
     * .@param prices 每天股价
     * .@return 最大利润
     */
    public int maxProfitDP(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        // hold = 第 i 天结束后“持有一股”时的最大利润（可能是历史买入后一直持有或今天买入）
        // cash = 第 i 天结束后“不持有”时的最大利润（可能是之前就空仓或今天刚卖出）
        int hold = -prices[0]; // 第一天选择买入：利润为 -prices[0]
        int cash = 0;          // 第一天选择不买：利润为 0
        for (int i = 1; i < prices.length; i++) {
            int todayPrice = prices[i];
            // 今天结束后不持有：保持昨天不持有 或 今天卖出昨天持有
            int nextCash = Math.max(cash, hold + todayPrice);
            // 今天结束后持有：保持昨天持有 或 今天用昨日 cash 买入
            int nextHold = Math.max(hold, cash - todayPrice);
            cash = nextCash;
            hold = nextHold;
        }
        return cash; // 最终答案：最后一天不持有的最大利润
    }

    /**
     * .校验两个实现是否一致（在本题语义下应该完全一致）
     */
    private void assertSame(int[] prices) {
        int greedyAns = maxProfit(prices);
        int dpAns = maxProfitDP(prices);
        if (greedyAns != dpAns) {
            throw new AssertionError("实现不一致: greedy=" + greedyAns + ", dp=" + dpAns);
        }
    }

    public static void main(String[] args) {
        S72_Easy_122_买卖股票的最佳时机_II solution = new S72_Easy_122_买卖股票的最佳时机_II();
        System.out.println("=== 买卖股票的最佳时机 II 测试开始 ===\n");

        // 测试1：题目示例1
        int[] case1 = {7, 1, 5, 3, 6, 4};
        testCase(solution, case1, 7, "示例1 上下波动两次盈利");

        // 测试2：题目示例2（持续上升）
        int[] case2 = {1, 2, 3, 4, 5};
        testCase(solution, case2, 4, "示例2 持续上升");

        // 测试3：题目示例3（持续下降）
        int[] case3 = {7, 6, 4, 3, 1};
        testCase(solution, case3, 0, "示例3 持续下降");

        // 测试4：单元素
        int[] case4 = {10};
        testCase(solution, case4, 0, "单元素 无交易");

        // 测试5：空数组
        int[] case5 = {};
        testCase(solution, case5, 0, "空数组");

        // 测试6：剧烈震荡
        int[] case6 = {2, 4, 1, 7}; // (4-2)+(7-1)=2+6=8
        testCase(solution, case6, 8, "剧烈震荡 两段收益");

        // 测试7：重复价格
        int[] case7 = {3, 3, 3, 3};
        testCase(solution, case7, 0, "全相等 无收益");

        // 测试8：V 形再上升
        int[] case8 = {5, 2, 4, 1, 3, 6}; // (4-2)+(3-1)+(6-3)=2+2+3=7
        testCase(solution, case8, 7, "多段组合 V形与上升");

        // 测试9：首尾峰谷
        int[] case9 = {1, 10, 2, 9}; // (10-1)+(9-2)=9+7=16
        testCase(solution, case9, 16, "首尾峰谷 两大段");

        // 测试10：长数组随机（手动构造）
        int[] case10 = {1, 5, 3, 8, 4, 9, 2, 6}; // (5-1)+(8-3)+(9-4)+(6-2)=4+5+5+4=18
        testCase(solution, case10, 18, "多次波动 长数组");

        // 额外一致性批量校验（可扩展）
        System.out.println("\n=== 随机一致性抽样校验（简易） ===");
        int[][] batch = {case1, case2, case3, case4, case5, case6, case7, case8, case9, case10};
        for (int i = 0; i < batch.length; i++) {
            try {
                solution.assertSame(batch[i]);
                System.out.println("用例" + (i + 1) + " -> 两种实现一致");
            } catch (AssertionError e) {
                System.out.println("用例" + (i + 1) + " -> 不一致: " + e.getMessage());
            }
        }

        System.out.println("\n=== 所有测试完成 ===");
    }

    private static void testCase(S72_Easy_122_买卖股票的最佳时机_II solution, int[] prices, int expected, String title) {
        System.out.println("--- " + title + " ---");
        System.out.print("输入 prices: [");
        for (int i = 0; i < prices.length; i++) {
            System.out.print(prices[i]);
            if (i < prices.length - 1) System.out.print(",");
        }
        System.out.println("]");
        int greedyAns = solution.maxProfit(prices);
        int dpAns = solution.maxProfitDP(prices);
        System.out.println("Greedy结果 = " + greedyAns + ", DP结果 = " + dpAns + ", 期望 = " + expected);
        assert greedyAns == expected : "贪心算法结果错误";
        assert dpAns == expected : "DP算法结果错误";
        assert greedyAns == dpAns : "两种实现不一致";
        System.out.println("✓ 用例通过\n");
    }
}
